/**
 * 
 */
package dp.passed;

import java.util.ArrayList;

/**
 * @author xyyi
 *
 */
public class PalindromePartitioning {

	/**
	Given a string s, partition s such that every substring of the partition is a palindrome.

	Return all possible palindrome partitioning of s.

	For example, given s = "aab",
	Return

	[
	["aa","b"],
	["a","a","b"]
	]
	 */
	public ArrayList<ArrayList<String>> partition(String s) {

		if (s == null || s.length() == 0)
			return null;
		ArrayList<ArrayList<String>> lists = new ArrayList<ArrayList<String>>();
		ArrayList<String> list = new ArrayList<String>();
		Boolean[][] dp = new Boolean[s.length()][s.length()];
		for (int i = 0; i < s.length(); i++) {
			for (int j = i; j < s.length(); j++) {
				palindrome(s, i, j, dp);
			}
		}

		partitionHelper(s, 0, lists, list, dp);
		return lists;
	}

	public void partitionHelper(String s, int index,
			ArrayList<ArrayList<String>> lists, ArrayList<String> list,
			Boolean[][] palindrome) {
		if (index == s.length()) {
			lists.add(new ArrayList<String>(list));
		} else {
			for (int i = index; i < s.length(); i++) {
				if (palindrome[index][i]) {
					list.add(s.substring(index, i + 1));
					partitionHelper(s, i + 1, lists, list, palindrome);
					list.remove(list.size() - 1);
				}
			}
		}
	}

	public void palindrome(String s, int begin, int end, Boolean[][] dp) {
		assert (begin <= end);

		if (begin == end) {
			dp[begin][end] = true;
		} else if (end - begin == 1) {
			dp[begin][end] = (s.charAt(begin) == s.charAt(end));
		} else {
			if (dp[begin + 1][end - 1] == null) {
				palindrome(s, begin + 1, end - 1, dp);
			}
			dp[begin][end] = dp[begin + 1][end - 1]
					&& (s.charAt(begin) == s.charAt(end));
		}
	}

	/**
	 * 
	 */
	public PalindromePartitioning() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
